⟸ Go Back ⟸
Exercise 9 (Homework 4).
(complement, context-free languages, hard exercise)

Complement of context-free sometimes is context-free

In general context-free languages are not closed under complement, that is given a context-free language L it is not true in general that \overline L is also context-free.

This exercise is about some context-free languages whose complement is actually also context-free.

  1. Give a non-ambiguous context-free grammar generating L=\{a^nb^n \mid n\in \mathbb N\} and a context-free grammar generating \overline L. Can you make this latter grammar non-ambiguous?

    Tip

    Use RACSO to test whether your proposed grammar for \overline L is non-ambiguous.

  2. Give a non-ambiguous context-free grammar generating L=\{w\in \{a,b\}^* \mid w=w^R\} and a context-free grammar generating \overline L. Can you make this latter grammar non-ambiguous?

    Tip

    Use RACSO to test whether your proposed grammar for \overline L is non-ambiguous.